Having established that Quick Sort offers one of the best average-case running times ($O(n \log n)$), we now examine its crucial practical properties: space efficiency and stability.
-
Space Complexity (Auxiliary Space): Quick Sort is typically executed In-Place, requiring minimal extra memory. However, its recursive nature uses the call stack.
- In the best/average case (balanced partitions), the recursion depth is $O(\log n)$, leading to an auxiliary space requirement of $O(\log n)$.
- In the worst case (unbalanced partitions), the depth can be $O(n)$. Optimized versions recur on the smaller partition first to guarantee $O(\log n)$ stack space.
- Stability: Quick Sort is generally considered Unstable. The partitioning phase, which involves swaps across the pivot, often disrupts the original relative order of elements with identical values.
- Achieving stability would require significant extra space, sacrificing Quick Sort's key In-Place advantage.
| Property | Average Case | Worst Case | Notes |
|---|---|---|---|
| Time Complexity | $O(n \log n)$ | $O(n^2)$ | Dependent on pivot selection and recurrence depth. |
| Auxiliary Space | $O(\log n)$ | $O(n)$ or $O(\log n)$ | Space for recursion stack. $O(\log n)$ achievable with optimization. |
| Stability | Unstable | Unstable | In-place partitioning violates stable ordering. |
| Type | Comparison | Comparison | Requires comparisons to determine relative order. |